#! /usr/bin/perl -w
use strict;
use warnings;
use Time::HiRes;
use Parallel::ForkManager;

my $g_start = Time::HiRes::time;
n_queen_main( @ARGV );



sub n_queen_main{
	my ( $max ) = valid_check( @ARGV );
	my $pfm = Parallel::ForkManager->new( 100 );
	foreach my $start ( 0 .. $max-1 ){
		$pfm->start and next;
		my $p_map   = mapping    ( $max  );
		$p_map->[0]->[$start] = 1;
		my( $a,$count ) = put_queen( $p_map, $max, 1, $start, 0 );
		print "PROCESS:$start, COUNT:$count\n";
		$pfm->finish;
	}
	$pfm->wait_all_children;
	my $time_record = Time::HiRes::time - $g_start;
	printf "経過時間：%f\n", $time_record;
}

sub print_map{
	my( $p_map, $max, $count, $output ) = @_;
	open( WP, ">>$output" );
	my $string = '';
	my $yoko = '+' . '---+' x $max;
	foreach my $y ( 0 .. $max - 1 ){
		print WP "$yoko\n";
		$string = '|';
		foreach my $x ( 0 .. $max - 1 ){
			$string .= $p_map->[ $x ]->[ $y ] ? ' Q |' : '   |';
		}
		print WP "$string\n";
	}
	print WP "$yoko\n";
	print WP "現在の回答は $count 個目です。\n";
	my $time_record = Time::HiRes::time - $g_start;
	printf WP "経過時間：%f\n", $time_record;
	print WP "\n\n";
	close( WP );
}

sub put_queen{
	my( $p_map, $max, $x, $process, $count ) = @_;
	if( $x >= $max ){
		$count++;
		#print_map( $p_map, $max, $count, './'.$process.'.txt' );
		return ( $p_map, $count );
	}
	foreach my $y ( 0 .. $max - 1 ){
		if( queen_check( $p_map, $max, $x, $y ) ){
			$p_map->[ $x ]->[ $y ] = 1;
			( $p_map, $count ) = put_queen( $p_map, $max, $x + 1, $process, $count );
			$p_map->[ $x ]->[ $y ] = 0;
		}
	}
	return ( $p_map, $count );
}

sub queen_check{
	my ( $p_map, $max, $x, $y ) = @_;
	my $flag = 1;
	foreach my $i ( 1 .. $x ){
		if( $p_map->[ $x - $i ]->[ $y ] ){
			$flag = 0;
		}
		if( $y + $i < $max ){
			if( $p_map->[ $x - $i ]->[ $y + $i ] ){
				$flag = 0;
			}
		}
		if( $y - $i >= 0 ){
			if( $p_map->[ $x - $i ]->[ $y - $i ] ){
				$flag = 0;
			}
		}
	}
	return $flag;
}

sub valid_check{
	my ( $value ) = @_;
	if(   !defined $value
	   || $value !~ /^\d+$/ ){
		$value = 8;
	}
	return $value;
}

sub mapping{
	my ( $max ) = @_;
	my $p_map;
	foreach my $y ( 0 .. $max - 1 ){
		foreach my $x ( 0 .. $max - 1 ){
			$p_map->[ $x ]->[ $y ] = 0;
		}
	}
	return $p_map;
}


1;
